package binary;

/**
 * 找出第一个大于目标元素的索引
 * https://mp.weixin.qq.com/s/1ExIav9uK4bvVnnf4t0H2Q
 *
 * @auther yang
 * @date 2022/3/18 10:38
 */
public class SearchGreaterThanTarget {

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 5, 6, 6, 8, 9, 11};
        int target = 3;
        System.out.println(search(nums, target));
    }

    private static int search(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (a[mid] > target) {                          // 大于目标值的情况
                if (mid == 0 || a[mid - 1] <= target) {     // 要考虑到 mid 的边界情况
                    return mid;
                }
                hi = mid - 1;
            } else if (a[mid] <= target) {                  // 小于目标值的情况
                lo = mid + 1;
            }
        }
        // 所有元素都小于目标值
        return -1;
    }
}
